package 中等.动态规划.其他;

/**
 * 给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分
 * ，并且两个景点 i 和 j 之间的 距离 为 j - i。
 * 一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，
 * 也就是景点的评分之和 减去 它们两者之间的距离。
 * <p>
 * 返回一对观光景点能取得的最高分。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/best-sightseeing-pair
 */
public class 最佳观光组合_1014 {

    public static void main(String[] args) {

        int[] values = new int[]{8, 1, 5, 2, 6};
        System.out.println(maxScoreSightseeingPair2(values));

    }

    /**
     * 动态规划
     * 1，子问题
     * 0，i之间的一对景点取得的最高分
     * 2，递推关系
     * 0，i-1的最高分为max
     * 加上i和之前所有值得评分，是否大于max
     * dp[i]=Math.max(max,dp[i-1]);
     * <p>
     * 每次都要获取当前景点和之前所有景点的评分，时间复杂度O(n*n)
     *
     * @param values
     * @return
     */
    public static int maxScoreSightseeingPair(int[] values) {
        int maxValue = values[0] + values[1] - 1;
        for (int cur = 2; cur < values.length; cur++) {
            int curValue = values[cur];
            for (int pre = 0; pre < cur; pre++) {
                maxValue = Math.max(maxValue, curValue + values[pre] + pre - cur);
            }
        }
        return maxValue;
    }

    /**
     * 对于当前景点来说，求当前景点的和之前景点的最高评分
     * 如果能够得到相对于当前景点，之前得最高评分
     * 最大评分=values[cur] + values[pre] + pre - cur
     * 分解：维护values[pre]+pre的最大值
     */
    public static int maxScoreSightseeingPair2(int[] values) {
        int ans = 0;
        int preMaxValue = values[0] + 0;
        for (int cur = 1; cur < values.length; cur++) {
            ans = Math.max(ans, preMaxValue + values[cur] - cur);
            preMaxValue = Math.max(preMaxValue, values[cur] + cur);
        }
        return ans;
    }

}
